import kotlin.math.abs
import kotlin.math.min

//有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
//
// 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下： 
//
// 
// 如果 x == y，那么两块石头都会被完全粉碎； 
// 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 
// 
//
// 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。 
//
// 
//
// 示例 1： 
//
// 
//输入：stones = [2,7,4,1,8,1]
//输出：1
//解释：
//组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
//组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
//组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
//组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
// 
//
// 示例 2： 
//
// 
//输入：stones = [31,26,33,21,40]
//输出：5
// 
//
// 示例 3： 
//
// 
//输入：stones = [1,2]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= stones.length <= 30 
// 1 <= stones[i] <= 100 
// 
// Related Topics 动态规划 
// 👍 257 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class SolutionlastStoneWeightII {
    @org.junit.Test
    fun test() {
        println(this.lastStoneWeightII(intArrayOf(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 14, 23, 37, 61, 98)))
    }

    private var map = mutableMapOf<String, Int>()

    private fun lastStoneWeightII(stones: IntArray): Int {
        // TODO("Not yet implemented")
        if (stones.isEmpty()) {
            return 0
        }
        if (stones.size == 1) {
            return stones[0]
        }
        if (stones.size == 2) {
            return abs(stones[1] - stones[0])
        }

        stones.sort()
        if (map.containsKey(stones.joinToString(","))) {
            return map[stones.joinToString(",")]!!
        }
        var ret = Int.MAX_VALUE
        // 循环所有可能
        for (index in stones.indices) {
            val itemArr = stones.copyOf()
            val dest = deleteItem(index, itemArr)
            for (destIndex in dest.indices) {
                val copyOf = dest.copyOf()
                // 生成新的数组
                copyOf[destIndex] = abs(copyOf[destIndex] - stones[index])
                // 找到新数组的最小值
                val minWeight = lastStoneWeightII(copyOf)
                // 比较当前循环中，最小值的合
                ret = min(ret, minWeight)
                if (ret == 0) {
                    break
                }
                println(ret.toString() + ":" + stones[index].toString() + "-" + minWeight)
            }
            if (ret == 0) {
                break
            }
        }
        map.put(stones.joinToString(","), ret)
        return ret
    }

    /**
     * 删除item
     * @index：删除位置下标
     * */
    fun deleteItem(index: Int, itemArr: IntArray): IntArray {
        var newArr = IntArray(itemArr.size - 1)
        for (i in newArr.indices) {
            if (i < index) {
                newArr[i] = itemArr[i]
            } else {
                newArr[i] = itemArr[i + 1]
            }
        }
        return newArr
    }
}
//leetcode submit region end(Prohibit modification and deletion)
